package top.minuy.structure.graph.route.hamilton;

import top.minuy.structure.graph.cc.bfs.CC;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 哈密尔顿回路算法
 *
 * @author Minuy
 * @time 9:21
 * @date 2021/11/23
 */
public class HamiltonLoop {
    Graph g;
    boolean[] isVisited;
    int[] pre;
    int end;

    public HamiltonLoop(Graph g) {
        this.g = g;

        isVisited = new boolean[g.V()];
        pre = new int[g.V()];

        end = -1;

        // 加上联通分量的判断会提升效率
        // 因为这个算法的时间复杂度非常高 : O(n!)
        CC cc = new CC(g);
        if (cc.count()==1) {
            // dfs(0,0);
            dfs(0, 0, g.V());
        }
        // 不是联通图，直接返回，不存在哈密尔顿回路
        // dfs(0, 0, g.V());
    }

    /* private boolean dfs(int v, int parent) {
        isVisited[v] = true;

        pre[v] = parent;  // 回溯后会覆盖掉之前的

        for (int w:g.adj(v)){
            if (!isVisited[w]){
                if(dfs(w, v)){
                    return true;
                }
            }else if (w == 0 && allVisited()){
                end = v; // 记录最后一个点
                return true;
            }
        }

        // 回溯
        isVisited[v] = false;
        return false;

    }

    private boolean allVisited() {
        for (boolean v : isVisited) {
            if (!v) {
                return false;
            }
        }
        return true;
    }

    */

    /**
     * 优化后的哈密尔顿回路求解方式
     *
     * @param v      当前顶点
     * @param parent 父顶点
     * @param left   还剩下多少节点没访问。可以不用遍历isVisited数组
     * @return boolean 是否找到哈密尔顿回路
     * @author Minuy
     * @date 2021/11/23 10:06
     */
    private boolean dfs(int v, int parent, int left) {
        isVisited[v] = true;
        pre[v] = parent;
        left--;

        // 如果是最后一个点了，并且与源点有边连接，那么说明肯定有个回路
        if (left == 0 && g.hasEdge(v, 0)) {
            end = v;
            return true;
        }

        for (int w : g.adj(v)) {
            if (!isVisited[w]) {
                if (dfs(w, v, left)) {
                    return true;
                }
            }
        }

        // 回溯
        isVisited[v] = false;
        return false;
    }


    public Iterable<Integer> loop() {
        ArrayList<Integer> ret = new ArrayList<>();
        if (end == -1) {
            return ret;
        }

        int cur = end;
        while (cur != 0) {
            ret.add(cur);
            cur = pre[cur];
        }
        ret.add(0);

        Collections.reverse(ret);
        return ret;
    }

    @Override
    public String toString() {
        return loop().toString();
    }
}
